package com.example.zzy.zzytest.algo.sort.nlognsort;

public class HeapSort {
    public static void main(String[] args) {
        int[] nums = new int[]{4, 6, 8, 5, 9};
        heapSort(nums);
        for (int num : nums) {
            System.out.print(num + ",");

        }
    }

    public static void heapSort(int[] arr) {
        //构建初始大顶堆
        buildMaxHeap(arr);

        //将最大值交换到数组最后，并从顶端递归调整大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            maxHeapify(arr, 0, i);
        }

    }

    /**
     * 构建初始大顶堆
     * 从最后一个非叶子节点开始调整大顶堆
     */
    public static void buildMaxHeap(int[] arr) {
        //从最后一个非叶子节点开始调整大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maxHeapify(arr, i, arr.length);
        }
    }

    /**
     * 【递归】调整大顶堆
     *
     * @param parentIndex 调整位置
     * @param heapSize    剩余未排序大小/剩余堆大小
     */
//    public static void maxHeapify(int[] arr, int parentIndex, int heapSize) {
//        int lChild = 2 * parentIndex + 1;
//        int rChild = lChild + 1;
//        //找出当前节点，和它的左右儿子的最大值的下标
//        int largestIndex = parentIndex;
//        if (lChild < heapSize && arr[lChild] > arr[largestIndex]) {
//            largestIndex = lChild;
//        }
//        if (rChild < heapSize && arr[rChild] > arr[largestIndex]) {
//            largestIndex = rChild;
//        }
//        //
//        if (parentIndex != largestIndex) {
//            //将最大值换到根节点
//            swap(arr, parentIndex, largestIndex);
//            //从子节点位置再开始调整堆
//            maxHeapify(arr, largestIndex, heapSize);
//        }
//    }

    /**
     * 【非递归】调整大顶堆
     *
     * @param parentIndex 调整位置
     * @param heapSize    剩余未排序大小/剩余堆大小
     */
    public static void maxHeapify(int[] arr, int parentIndex, int heapSize) {
        int parentValue = arr[parentIndex];
        //左儿子index
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < heapSize) {
            //如果存在右儿子且比左儿子的值还大，则定位到右儿子
            if (childIndex + 1 < heapSize && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            //父节点比子节点大，则对于父节点已经是大顶堆
            if (parentValue >= arr[childIndex]) {
                break;
            } else {
                //把子节点最大值直接赋值给父节点
                arr[parentIndex] = arr[childIndex];
                //父子节点下移，去平衡下层的堆
                parentIndex = childIndex;
                childIndex = 2 * childIndex + 1;
            }

        }
        //最后把最开始父节点的值给到应该在的父节点位置
        arr[parentIndex] = parentValue;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
